package com.gitee.wsl.ext.array

/**
 * 时间复杂度O(n)  空间复杂度O(n)
 * 1、使用map 对所有的数 进行排序O(n)
 * 2、对map 进行查找，value 大于3的key
 */
fun IntArray.majorityElement(times:Int = size / 3): List<Int> {

    val map = mutableMapOf<Int, Int>()

    for (i in this) {
        if (map.containsKey(i)) {
            map[i] = map[i]?.plus(1)!!
        } else {
            map[i] = 1
        }
    }


    val l = mutableListOf<Int>()
    for (m in map) {

        if (m.value > times) {
            l.add(m.key)
        }
    }

    return l
}